package org.basic.algorithm.medium.offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
 * candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 * 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
 * <p>
 * 示例 1：
 * 输入: candidates = [2,3,6,7], target = 7
 * 输出: [[7],[2,2,3]]
 * <p>
 * 示例 2：
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 * <p>
 * 示例 3：
 * 输入: candidates = [2], target = 1
 * 输出: []
 * <p>
 * 示例 4：
 * 输入: candidates = [1], target = 1
 * 输出: [[1]]
 * <p>
 * 示例 5：
 * 输入: candidates = [1], target = 2
 * 输出: [[1,1]]
 * <p>
 * 提示：
 * 1 <= candidates.length <= 30
 * 1 <= candidates[i] <= 200
 * 1 <= target <= 500
 * <p>
 * candidate 中的每个元素都是独一无二的。
 *
 * @author LiKun
 * @date 2021/10/26 17:05
 */
public class NotRepeatElementCollection {
    public static List<List<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {
        System.out.println(combinationSum(new int[]{1, 2, 3}, 5));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);

        recursion(candidates, target, 0, new ArrayList<>(0));

        return result;
    }

    /**
     * 递归处理数组，并将结果放入到 result 集合中
     *
     * @param candidates   源数组
     * @param target       给定的值
     * @param index        本次便利起始索引
     * @param parContainer 本次便利存放结果集
     */
    private static void recursion(int[] candidates, int target, int index, List<Integer> parContainer) {
        // 使用 index 的好处：减少遍历次数；不需要对最终结果进行去重(例：不会出现 [[3, 5, 5], [5, 3, 5], [5, 5, 3]] 的情况)；
        for (; index < candidates.length && candidates[index] <= target; index++) {
            if (candidates[index] << 1 <= target) {                        // candidates[index] <= target - candidates[index] ---> 还存在可能被选取的值
                List<Integer> container = new ArrayList<>(parContainer);
                container.add(candidates[index]);

                recursion(candidates, target - candidates[index], index, container);
            } else if (candidates[index] == target) {                      // 本轮递归结束条件 ---> 最后一个被选取的值
                parContainer.add(candidates[index]);
                result.add(parContainer);
                break;
            }
        }
    }
}
